package demo03;

import java.util.Arrays;

public class QuickSort02 {
    public static void main(String[] args) {
        int[] a = {5,3,7,2,1,9,8,4};
        quickSort(a,0,a.length - 1);
        System.out.println(Arrays.toString(a));
    }
    /*
    双边循环快排:
            (1) :选择最左元素作为基准点元素
            (2) j 指针负责从右向左找比基准点小的元素,i 指针负责从左向右找比基准点大的元素
    旦找到两者交换位置，直至 i，i 相交
            (3) 最后基准点i交换，i 即为分区的位置
    */
    private static void swap(int[] arr,int i,int j){
        int t= arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private static int partition(int[] a, int l, int h) {
        int pv = a[l];
        int i = l;
        int j = h;
        while(i < j) {
            while(i < j && a[j] > pv){
                j--;
            }
            while(i < j && a[i] <= pv){
                i++;
            }
            if(i < j){
                swap(a,i,j);
            }
        }
        swap(a,l,j);
        return j;
    }
    public static void quickSort(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h); // 使用正确的左边界
        quickSort(a, l, p - 1); // 左分区
        quickSort(a, p + 1, h); // 右分区
    }



}
